{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Detect Cycles in 2D Grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: containsCycle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二维网格图中探测环"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二维字符网格数组&nbsp;<code>grid</code>&nbsp;，大小为&nbsp;<code>m x n</code>&nbsp;，你需要检查&nbsp;<code>grid</code>&nbsp;中是否存在 <strong>相同值</strong> 形成的环。</p>\n",
    "\n",
    "<p>一个环是一条开始和结束于同一个格子的长度 <strong>大于等于 4</strong>&nbsp;的路径。对于一个给定的格子，你可以移动到它上、下、左、右四个方向相邻的格子之一，可以移动的前提是这两个格子有 <strong>相同的值&nbsp;</strong>。</p>\n",
    "\n",
    "<p>同时，你也不能回到上一次移动时所在的格子。比方说，环&nbsp;&nbsp;<code>(1, 1) -&gt; (1, 2) -&gt; (1, 1)</code>&nbsp;是不合法的，因为从 <code>(1, 2)</code>&nbsp;移动到 <code>(1, 1)</code> 回到了上一次移动时的格子。</p>\n",
    "\n",
    "<p>如果 <code>grid</code>&nbsp;中有相同值形成的环，请你返回 <code>true</code>&nbsp;，否则返回 <code>false</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/08/22/5482e1.png\" style=\"height: 152px; width: 231px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>grid = [[&quot;a&quot;,&quot;a&quot;,&quot;a&quot;,&quot;a&quot;],[&quot;a&quot;,&quot;b&quot;,&quot;b&quot;,&quot;a&quot;],[&quot;a&quot;,&quot;b&quot;,&quot;b&quot;,&quot;a&quot;],[&quot;a&quot;,&quot;a&quot;,&quot;a&quot;,&quot;a&quot;]]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>如下图所示，有 2 个用不同颜色标出来的环：\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/08/22/5482e11.png\" style=\"height: 163px; width: 225px;\">\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/08/22/5482e2.png\" style=\"height: 154px; width: 236px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>grid = [[&quot;c&quot;,&quot;c&quot;,&quot;c&quot;,&quot;a&quot;],[&quot;c&quot;,&quot;d&quot;,&quot;c&quot;,&quot;c&quot;],[&quot;c&quot;,&quot;c&quot;,&quot;e&quot;,&quot;c&quot;],[&quot;f&quot;,&quot;c&quot;,&quot;c&quot;,&quot;c&quot;]]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>如下图所示，只有高亮所示的一个合法环：\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/08/22/5482e22.png\" style=\"height: 157px; width: 229px;\">\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/08/22/5482e3.png\" style=\"height: 120px; width: 183px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>grid = [[&quot;a&quot;,&quot;b&quot;,&quot;b&quot;],[&quot;b&quot;,&quot;z&quot;,&quot;b&quot;],[&quot;b&quot;,&quot;b&quot;,&quot;a&quot;]]\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m &lt;= 500</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 500</code></li>\n",
    "\t<li><code>grid</code>&nbsp;只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [detect-cycles-in-2d-grid](https://leetcode.cn/problems/detect-cycles-in-2d-grid/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [detect-cycles-in-2d-grid](https://leetcode.cn/problems/detect-cycles-in-2d-grid/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"a\",\"a\",\"a\",\"a\"],[\"a\",\"b\",\"b\",\"a\"],[\"a\",\"b\",\"b\",\"a\"],[\"a\",\"a\",\"a\",\"a\"]]', '[[\"c\",\"c\",\"c\",\"a\"],[\"c\",\"d\",\"c\",\"c\"],[\"c\",\"c\",\"e\",\"c\"],[\"f\",\"c\",\"c\",\"c\"]]', '[[\"a\",\"b\",\"b\"],[\"b\",\"z\",\"b\"],[\"b\",\"b\",\"a\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.n = n\n",
    "        self.setCount = n\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "    \n",
    "    def findset(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def unite(self, x: int, y: int):\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.setCount -= 1\n",
    "    \n",
    "    def findAndUnite(self, x: int, y: int) -> bool:\n",
    "        parentX, parentY = self.findset(x), self.findset(y)\n",
    "        if parentX != parentY:\n",
    "            self.unite(parentX, parentY)\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        uf = UnionFind(m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i > 0 and grid[i][j] == grid[i - 1][j]:\n",
    "                    if not uf.findAndUnite(i * n + j, (i - 1) * n + j):\n",
    "                        return True\n",
    "                if j > 0 and grid[i][j] == grid[i][j - 1]:\n",
    "                    if not uf.findAndUnite(i * n + j, i * n + j - 1):\n",
    "                        return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class setUnion(object):\n",
    "    def __init__(self,size):\n",
    "        self.parent=list(range(size))\n",
    "        self.rank=[1]*size\n",
    "        self.setCount=size\n",
    "    def find(self,i):\n",
    "        if self.parent[i]==i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parent[i]=self.find(self.parent[i])\n",
    "            return self.parent[i]\n",
    "    def union(self,i,j):\n",
    "        x,y=self.find(i),self.find(j)\n",
    "        if x==y:\n",
    "            return\n",
    "        if self.rank[x]<self.rank[y]:\n",
    "            x,y=y,x\n",
    "        self.rank[x]+=self.rank[y]\n",
    "        self.parent[y]=x\n",
    "        self.setCount-=1\n",
    "    def is_connected(self,i,j):\n",
    "        return self.find(i)==self.find(j)\n",
    "    def get_partset(self):\n",
    "        part=defaultdict(list)\n",
    "        for i in range(len(self.parent)):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        #判断图中是否存在环,可以使用经典的并查集相关算法,二维图并查集连接只用考虑互相垂直的两个方向,避免重复相连。\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        kkk=setUnion(m*n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for x,y in [(0,1),(1,0)]:\n",
    "                    new_i,new_j=i+x,j+y\n",
    "                    if 0<=new_i<m and 0<=new_j<n and grid[i][j]==grid[new_i][new_j]:\n",
    "                        if kkk.is_connected(i*n+j,new_i*n+new_j): return True\n",
    "                        else: kkk.union(i*n+j,new_i*n+new_j)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class setUnion(object):\n",
    "    def __init__(self,size):\n",
    "        self.parent=list(range(size))\n",
    "        self.rank=[1]*size\n",
    "        self.setCount=size\n",
    "    def find(self,i):\n",
    "        if self.parent[i]==i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parent[i]=self.find(self.parent[i])\n",
    "            return self.parent[i]\n",
    "    def union(self,i,j):\n",
    "        x,y=self.find(i),self.find(j)\n",
    "        if x==y:\n",
    "            return\n",
    "        if self.rank[x]<self.rank[y]:\n",
    "            x,y=y,x\n",
    "        self.rank[x]+=self.rank[y]\n",
    "        self.parent[y]=x\n",
    "        self.setCount-=1\n",
    "    def is_connected(self,i,j):\n",
    "        return self.find(i)==self.find(j)\n",
    "    def get_partset(self):\n",
    "        part=defaultdict(list)\n",
    "        for i in range(len(self.parent)):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        #判断图中是否存在环,可以使用经典的并查集相关算法\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        kkk=setUnion(m*n)\n",
    "        ch_set=set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for x,y in [(0,1),(1,0)]:\n",
    "                    new_i,new_j=i+x,j+y\n",
    "                    if 0<=new_i<m and 0<=new_j<n and grid[i][j]==grid[new_i][new_j]:\n",
    "                        if kkk.is_connected(i*n+j,new_i*n+new_j): return True\n",
    "                        else: kkk.union(i*n+j,new_i*n+new_j)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UFS:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.r = [0] * n\n",
    "        self.f = list(range(n))\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.f[x] != x:\n",
    "            self.f[x] = self.find(self.f[x])\n",
    "        return self.f[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        x, y = self.f[x], self.f[y]\n",
    "        if self.r[x] > self.r[y]:\n",
    "            self.f[y] = x\n",
    "        elif self.r[x] < self.r[y]:\n",
    "            self.f[x] = y\n",
    "        else:\n",
    "            self.f[y] = x\n",
    "            self.r[x] += 1\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        uf = UFS(m * n)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i > 0 and grid[i][j] == grid[i-1][j]:\n",
    "                    idx = i * n + j\n",
    "                    leftidx = (i - 1) * n + j\n",
    "                    if uf.find(idx) != uf.find(leftidx):\n",
    "                        uf.union(idx, leftidx)\n",
    "                    else:\n",
    "                        return True\n",
    "                if j > 0 and grid[i][j] == grid[i][j-1]:\n",
    "                    idx = i * n + j\n",
    "                    topidx = i * n + j - 1\n",
    "                    if uf.find(idx) != uf.find(topidx):\n",
    "                        uf.union(idx, topidx)\n",
    "                    else:\n",
    "                        return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        p = [i for i in range(m * n)]  # parents\n",
    "\n",
    "        def find(x):\n",
    "            while x!=p[x]:\n",
    "                p[x] = p[p[x]]\n",
    "                x=p[x]\n",
    "            return x\n",
    "        \n",
    "        def union(x, y):\n",
    "            rx, ry = find(x), find(y)\n",
    "            if rx == ry:\n",
    "                return True\n",
    "            p[ry] = rx\n",
    "            return False\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x = grid[i][j]\n",
    "                if i > 0 and grid[i-1][j] == x:\n",
    "                    if union(i * n + j, (i - 1) * n + j):\n",
    "                        return True\n",
    "                if j > 0 and grid[i][j-1] == x:\n",
    "                    if union(i * n + j, i * n + j - 1):\n",
    "                        return True\n",
    "\n",
    "        print(p)\n",
    "        # print(s)\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Union_Find():\n",
    "    def __init__(self, n):\n",
    "        self.fa = [_ for _ in range(n)]\n",
    "        self.num_count = [1 for _ in range(n)]\n",
    "\n",
    "    def findfa(self, x):\n",
    "        if x == self.fa[x]:\n",
    "            return x\n",
    "        else:\n",
    "            self.fa[x] = self.findfa(self.fa[x])\n",
    "            return self.fa[x]\n",
    "\n",
    "    def merge(self, a, b):\n",
    "        root_a = self.findfa(a)\n",
    "        root_b = self.findfa(b)\n",
    "        if (root_a == root_b):\n",
    "            return True\n",
    "    \n",
    "        if self.num_count[root_b] > self.num_count[root_a]:\n",
    "            root_a, root_b = root_b, root_a\n",
    "        # b的根节点变成a的子节点\n",
    "        self.fa[root_b] = root_a\n",
    "        # a节点合并b节点\n",
    "        self.num_count[root_a] += self.num_count[root_b]\n",
    "        # b节点数量变0\n",
    "        self.num_count[root_b] = 0\n",
    "        return False\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        ROW, COL = len(grid), len(grid[0])\n",
    "        uf = Union_Find(ROW * COL)\n",
    "        for row in range(ROW):\n",
    "            for col in range(COL):\n",
    "                # print(f\"row{row}, col{col}\")\n",
    "                index = row * COL + col\n",
    "                # 检查上面一格能否形成环\n",
    "                if 0 <= row - 1 < ROW and grid[row][col] == grid[row - 1][col]:\n",
    "                    index_up = index - COL\n",
    "                    # print(f\"index:{index}, index_up:{index_up}\")\n",
    "                    if uf.merge(index, index_up) == True:\n",
    "                        return True\n",
    "                if 0 <= col - 1 < COL and grid[row][col] == grid[row][col -1]:\n",
    "                    index_left = index - 1\n",
    "                    # print(f\"index:{index}, index_left:{index_left}\")\n",
    "                    if uf.merge(index, index_left):\n",
    "                        return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:                        #自定义 标准并查集模板\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = [x for x in range(n)]\n",
    "        self.size = [1 for _ in range(n)]\n",
    "        self.part = n\n",
    "\n",
    "    def Find(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        return self.Find(self.parent[x])\n",
    "    \n",
    "    def Union(self, x: int, y: int) -> bool:\n",
    "        root_x = self.Find(x)\n",
    "        root_y = self.Find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] > self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.parent[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        self.part -= 1\n",
    "        return True\n",
    "    \n",
    "    def inthesamepart(self, x: int, y: int) -> bool:\n",
    "        return self.Find(x) == self.Find(y)\n",
    "    \n",
    "    def getpartsize(self, x: int) -> int:\n",
    "        root_x = self.Find(x)\n",
    "        return self.size[root_x]\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        R, C = len(grid), len(grid[0])\n",
    "        UF = UnionFind(R * C)\n",
    "        for r in range(R):\n",
    "            for c in range(C):\n",
    "                ID = r * C + c\n",
    "                if 0 <= r-1 < R and grid[r-1][c] == grid[r][c]:\n",
    "                    ID_up = (r-1) * C + c\n",
    "                    if UF.inthesamepart(ID, ID_up) == True:     #可以直接用UF.Union判断     但这样写思路更清晰\n",
    "                        return True\n",
    "                    else:\n",
    "                        UF.Union(ID, ID_up)\n",
    "                if 0 <= c-1 < C and grid[r][c-1] == grid[r][c]:\n",
    "                    ID_left = r * C + c-1\n",
    "                    if UF.inthesamepart(ID, ID_left) == True:   #可以直接用UF.Union判断     但这样写思路更清晰\n",
    "                        return True\n",
    "                    else:\n",
    "                        UF.Union(ID, ID_left)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.parents = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.cnt = n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parents[x] == x:\n",
    "            return x\n",
    "        self.parents[x] = self.find(self.parents[x])\n",
    "        return self.parents[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parents[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.cnt -= 1\n",
    "    \n",
    "    def find_and_union(self, x, y):\n",
    "        parent_x, parent_y = self.find(x), self.find(y)\n",
    "        if parent_x != parent_y:\n",
    "            self.union(parent_x, parent_y)\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        uf = UnionFind(m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i > 0 and grid[i][j] == grid[i-1][j]:\n",
    "                    if not uf.find_and_union(i*n+j, (i-1)*n+j):\n",
    "                        return True\n",
    "                if j > 0 and grid[i][j] == grid[i][j-1]:\n",
    "                    if not uf.find_and_union(i*n+j, i*n+j-1):\n",
    "                        return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Dsu:\n",
    "    def __init__(self,n):\n",
    "        self.fa = list(range(n))\n",
    "    def find(self,x):\n",
    "        if self.fa[x] != x:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "    def merge(self,x,y):\n",
    "        Root_x = self.find(x)\n",
    "        Root_y = self.find(y)\n",
    "        if Root_x == Root_y:\n",
    "            return True\n",
    "        self.fa[Root_x] = Root_y\n",
    "        return False\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dsu = Dsu(m*n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 每个格子连接它左边和上边的格子\n",
    "                if i > 0 and grid[i][j] == grid[i-1][j]:\n",
    "                    if dsu.merge(i*n+j,(i-1)*n+j):\n",
    "                        return True\n",
    "                if j > 0 and grid[i][j] == grid[i][j-1]:\n",
    "                    if dsu.merge(i*n+j,i*n + j-1):\n",
    "                        return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.n = n\n",
    "        self.setCount = n\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "    \n",
    "    def findset(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def unite(self, x: int, y: int):\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.setCount -= 1\n",
    "    \n",
    "    def findAndUnite(self, x: int, y: int) -> bool:\n",
    "        parentX, parentY = self.findset(x), self.findset(y)\n",
    "        if parentX != parentY:\n",
    "            self.unite(parentX, parentY)\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        uf = UnionFind(m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i > 0 and grid[i][j] == grid[i - 1][j]:\n",
    "                    if not uf.findAndUnite(i * n + j, (i - 1) * n + j):\n",
    "                        return True\n",
    "                if j > 0 and grid[i][j] == grid[i][j - 1]:\n",
    "                    if not uf.findAndUnite(i * n + j, i * n + j - 1):\n",
    "                        return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.fa = [x for x in range(self.n)]\n",
    "        self.rank = [1] * self.n\n",
    "        self.count = self.n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.fa[x] != x:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx == fy:\n",
    "            return False\n",
    "        if self.rank[fx] < self.rank[fy]:\n",
    "            fx, fy = fy, fx\n",
    "        self.rank[fx] = self.rank[fy]+1\n",
    "        self.fa[fy] = fx\n",
    "        self.count -= 1\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        size = m * n\n",
    "        uf = UnionFind(size)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i > 0 and grid[i][j] == grid[i - 1][j]:\n",
    "                    if not uf.union(i * n + j, (i - 1) * n + j):\n",
    "                        return True\n",
    "                if j > 0 and grid[i][j] == grid[i][j - 1]:\n",
    "                    if not uf.union(i * n + j, i * n + j - 1):\n",
    "                        return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UFS:\n",
    "    def __init__(self, n):\n",
    "        self.f = list(range(n))\n",
    "        self.r = [0] * n\n",
    "        self.n = n\n",
    "    \n",
    "    def find(self, x):\n",
    "        if not self.f[x] == x:\n",
    "            self.f[x] = self.find(self.f[x])\n",
    "        return self.f[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if self.r[x] < self.r[y]:\n",
    "            self.f[x] = y\n",
    "        elif self.r[x] > self.r[y]:\n",
    "            self.f[y] = x\n",
    "        else:\n",
    "            self.f[y] = x\n",
    "            self.r[x] += 1\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        uf = UFS(m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 和左边比\n",
    "                if i > 0 and grid[i][j] == grid[i-1][j]:\n",
    "                    idx = i * n + j\n",
    "                    leftidx = (i - 1) * n + j\n",
    "                    if uf.find(idx) != uf.find(leftidx):\n",
    "                        uf.union(idx, leftidx)\n",
    "                    else:\n",
    "                        return True\n",
    "                if j > 0 and grid[i][j] == grid[i][j-1]:\n",
    "                    idx = i * n + j\n",
    "                    topidx = i * n + j - 1\n",
    "                    if uf.find(idx) != uf.find(topidx):\n",
    "                        uf.union(idx, topidx)\n",
    "                    else:\n",
    "                        return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "\n",
    "        def getnxt(x, y, m, n):\n",
    "            ans = []\n",
    "            dirs = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx <= m-1 and 0 <= ny <= n-1:\n",
    "                    ans.append((nx, ny))\n",
    "            return ans\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        vis = [[False] * n for _ in range(m)]\n",
    "\n",
    "\n",
    "        def bfs(x, y):\n",
    "            nonlocal vis\n",
    "            q = deque([(x, y, -1, -1)])\n",
    "            vis[x][y] = True\n",
    "\n",
    "            while q:\n",
    "                x, y, px, py = q.popleft()\n",
    "                for nx, ny in getnxt(x, y, m, n):\n",
    "                    # 除了边界要求外，还需要新位置不等于旧位置，且新位置值和当前值相等\n",
    "                    if (px != nx or py != ny) and grid[nx][ny] == grid[x][y]:\n",
    "                        if vis[nx][ny] == True:\n",
    "                            return True\n",
    "                        else:\n",
    "                            q.append((nx, ny, x, y))\n",
    "                            vis[nx][ny] = True\n",
    "            return False\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if vis[i][j]:\n",
    "                    continue\n",
    "                if bfs(i, j):\n",
    "                    return True\n",
    "        \n",
    "        return False\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        # 遇到网格图论问题，尽可能转化成有向图处理，无向图注定是难的\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        p = [i for i in range(m*n)]\n",
    "        def find(node):\n",
    "            while p[node] != node:\n",
    "                p[node] = p[p[node]]\n",
    "                node = p[node]\n",
    "            return node\n",
    "\n",
    "        def union(a, b):\n",
    "            root_a, root_b = find(a), find(b)\n",
    "            if root_a == root_b:\n",
    "                return True\n",
    "            p[root_a] = root_b\n",
    "            return False\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i > 0 and grid[i][j] == grid[i-1][j]:\n",
    "                    if union(i*n+j, (i-1)*n+j):\n",
    "                        return True\n",
    "                if j > 0 and grid[i][j] == grid[i][j-1]:\n",
    "                    if union(i*n+j, i*n+(j-1)):\n",
    "                        return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.n = n\n",
    "        self.setCount = n\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "    \n",
    "    def findset(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def unite(self, x: int, y: int):\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.setCount -= 1\n",
    "    \n",
    "    def findAndUnite(self, x: int, y: int) -> bool:\n",
    "        parentX, parentY = self.findset(x), self.findset(y)\n",
    "        if parentX != parentY:\n",
    "            self.unite(parentX, parentY)\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        uf = UnionFind(m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i > 0 and grid[i][j] == grid[i - 1][j]:\n",
    "                    if not uf.findAndUnite(i * n + j, (i - 1) * n + j):\n",
    "                        return True\n",
    "                if j > 0 and grid[i][j] == grid[i][j - 1]:\n",
    "                    if not uf.findAndUnite(i * n + j, i * n + j - 1):\n",
    "                        return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\r\n",
    "        m,n = len(grid), len(grid[0])\r\n",
    "        # 不是深搜,应该广搜\r\n",
    "\r\n",
    "        vis = [[False] * n for _ in range(m)]\r\n",
    "\r\n",
    "        def bfs(i: int, j: int) -> bool:\r\n",
    "            q = [(i, j)]\r\n",
    "            while q:\r\n",
    "                tmp = q \r\n",
    "                q = []\r\n",
    "                scur = set()\r\n",
    "                for x, y in tmp:\r\n",
    "                    for nx, ny in (x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1):\r\n",
    "                        if 0 <= nx < m and 0 <= ny < n and not vis[nx][ny] and grid[nx][ny] == grid[x][y]:\r\n",
    "                            if (nx, ny) in scur:\r\n",
    "                                return True \r\n",
    "                            scur.add((nx, ny))\r\n",
    "                            q.append((nx, ny))\r\n",
    "                for x, y in scur:\r\n",
    "                    vis[x][y] = True \r\n",
    "            return False \r\n",
    "            \r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                if not vis[i][j]:\r\n",
    "                    vis[i][j] = True \r\n",
    "                    if bfs(i, j):\r\n",
    "                        return True \r\n",
    "        return False \r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class setUnion(object):\n",
    "    def __init__(self,size):\n",
    "        self.parent=list(range(size))\n",
    "        self.rank=[1]*size\n",
    "        self.setCount=size\n",
    "    def find(self,i):\n",
    "        if self.parent[i]==i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parent[i]=self.find(self.parent[i])\n",
    "            return self.parent[i]\n",
    "    def union(self,i,j):\n",
    "        x,y=self.find(i),self.find(j)\n",
    "        if x==y:\n",
    "            return\n",
    "        if self.rank[x]<self.rank[y]:\n",
    "            x,y=y,x\n",
    "        self.rank[x]+=self.rank[y]\n",
    "        self.parent[y]=x\n",
    "        self.setCount-=1\n",
    "    def is_connected(self,i,j):\n",
    "        return self.find(i)==self.find(j)\n",
    "    def get_partset(self):\n",
    "        part=defaultdict(list)\n",
    "        for i in range(len(self.parent)):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        kkk=setUnion(m*n)\n",
    "        ch_set=set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for x,y in [(0,1),(1,0)]:\n",
    "                    new_i,new_j=i+x,j+y\n",
    "                    if 0<=new_i<m and 0<=new_j<n and grid[i][j]==grid[new_i][new_j]:\n",
    "                        if kkk.is_connected(i*n+j,new_i*n+new_j): return True\n",
    "                        else: kkk.union(i*n+j,new_i*n+new_j)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 核心思想：并查集\n",
    "class Dsu:\n",
    "    def __init__(self,n):\n",
    "        self.fa = list(range(n))\n",
    "    def find(self,x):\n",
    "        if self.fa[x] != x:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "    def merge(self,x,y):\n",
    "        Root_x = self.find(x)\n",
    "        Root_y = self.find(y)\n",
    "        if Root_x == Root_y:\n",
    "            return True\n",
    "        self.fa[Root_x] = Root_y\n",
    "        return False\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        # 连接方法，连接右边和下面\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        dsu = Dsu(m*n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # i,j\n",
    "                # 连接右边 i,j+1\n",
    "                # 连接下面 i+1,j\n",
    "                if j+1 < n and grid[i][j] == grid[i][j+1]:\n",
    "                    if dsu.merge(i*n+j,i*n+j+1):\n",
    "                        return True\n",
    "                if i+1 < m and grid[i][j] == grid[i+1][j]:\n",
    "                    if dsu.merge(i*n+j,(i+1)*n+j):\n",
    "                        return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.fa = [x for x in range(self.n)]\n",
    "        self.rank = [1] * self.n\n",
    "        self.count = self.n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.fa[x] != x:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx == fy:\n",
    "            return False\n",
    "        if self.rank[fx] < self.rank[fy]:\n",
    "            fx, fy = fy, fx\n",
    "        self.rank[fx] += self.rank[fy]\n",
    "        self.fa[fy] = fx\n",
    "        self.count -= 1\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        size = m * n\n",
    "        uf = UnionFind(size)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i > 0 and grid[i][j] == grid[i - 1][j]:\n",
    "                    if not uf.union(i * n + j, (i - 1) * n + j):\n",
    "                        return True\n",
    "                if j > 0 and grid[i][j] == grid[i][j - 1]:\n",
    "                    if not uf.union(i * n + j, i * n + j - 1):\n",
    "                        return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [0] * n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "\n",
    "    def find_union(self, x, y):\n",
    "        parent_x, parent_y = self.find(x), self.find(y)\n",
    "        if parent_x != parent_y:\n",
    "            self.union(parent_x, parent_y)\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        # m, n = len(grid), len(grid[0])\n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         ch, target_pos = grid[i][j], (i, j)\n",
    "        #         q = deque([(i, j, 0, {(i, j)})])\n",
    "        #         while q:\n",
    "        #             x, y, distance, visited = q.popleft()\n",
    "        #             for xx, yy in ((x-1, y), (x+1, y), (x, y-1), (x, y+1)):\n",
    "        #                 if 0 <= xx < m and 0 <= yy < n and grid[xx][yy] == ch:\n",
    "        #                     if (xx, yy) == target_pos and distance >= 3:\n",
    "        #                         return True\n",
    "        #                     if (xx, yy) not in visited:\n",
    "        #                         q.append((xx, yy, distance+1, visited | {(xx, yy)}))\n",
    "        # return False\n",
    "\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        uf = UnionFind(m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i > 0 and grid[i][j] == grid[i - 1][j]:\n",
    "                    if not uf.find_union(i * n + j, (i - 1) * n + j):\n",
    "                        return True\n",
    "                if j > 0 and grid[i][j] == grid[i][j - 1]:\n",
    "                    if not uf.find_union(i * n + j, i * n + j - 1):\n",
    "                        return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        fa = [i for i in range(m*n)]\n",
    "        dirs = [[1,0],[-1,0],[0,1],[0,-1]]\n",
    "        visit = [[False for i in range(n)] for j in range(m)] \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                visit[i][j] = True\n",
    "                numid = self.getid(i, j, n)\n",
    "                for dirr in dirs:\n",
    "                    nx = i+dirr[0]\n",
    "                    ny = j + dirr[1]\n",
    "                    numnid = self.getid(nx, ny, n)\n",
    "                    if (nx < 0 or ny<0 or nx >= m or ny >= n or grid[nx][ny] != grid[i][j] or visit[nx][ny] == True):\n",
    "                        continue\n",
    "                    if self.find(numid, fa) != self.find(numnid, fa):\n",
    "                        self.union(numid, numnid , fa)\n",
    "                    else:\n",
    "                        return True\n",
    "        return False\n",
    "\n",
    "    \n",
    "    def find(self,x,fa):\n",
    "        if fa[x] == x:\n",
    "            return x\n",
    "        fa[x] = self.find(fa[x], fa)\n",
    "        return fa[x]\n",
    "    \n",
    "    def union(self,x,y,fa):\n",
    "        fa[self.find(x,fa)] = self.find(y, fa)\n",
    "    \n",
    "    def getid(self,x,y,col):\n",
    "        return x*col+y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.visited = []\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        self.visited = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if self.visited[i][j] != 0:\n",
    "                    continue\n",
    "                queue = [(i, j)]\n",
    "                self.visited[i][j] = 1\n",
    "                while len(queue):\n",
    "                    valid_num = 0\n",
    "                    x, y = queue[0]\n",
    "                    queue.pop(0)\n",
    "                    if x > 0:\n",
    "                        if self.visited[x-1][y] and grid[x-1][y] == grid[i][j]:\n",
    "                            valid_num += 1\n",
    "                        if not self.visited[x-1][y] and grid[x-1][y] == grid[i][j]:\n",
    "                            self.visited[x-1][y] = 1\n",
    "                            queue.append((x-1, y))\n",
    "                    if x < m - 1:\n",
    "                        if self.visited[x+1][y] and grid[x+1][y] == grid[i][j]:\n",
    "                            valid_num += 1\n",
    "                        if not self.visited[x+1][y] and grid[x+1][y] == grid[i][j]:\n",
    "                            self.visited[x+1][y] = 1\n",
    "                            queue.append((x+1, y))\n",
    "                    if y > 0:\n",
    "                        if self.visited[x][y-1] and grid[x][y-1] == grid[i][j]:\n",
    "                            valid_num += 1\n",
    "                        if not self.visited[x][y-1] and grid[x][y-1] == grid[i][j]:\n",
    "                            self.visited[x][y-1] = 1\n",
    "                            queue.append((x, y-1))\n",
    "                    if y < n - 1:\n",
    "                        if self.visited[x][y+1] and grid[x][y+1] == grid[i][j]:\n",
    "                            valid_num += 1\n",
    "                        if not self.visited[x][y+1] and grid[x][y+1] == grid[i][j]:\n",
    "                            self.visited[x][y+1] = 1\n",
    "                            queue.append((x, y+1))\n",
    "                    if valid_num > 1:\n",
    "                        print(x, y)\n",
    "                        print(self.visited)\n",
    "                        return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [0] * n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "\n",
    "    def find_union(self, x, y):\n",
    "        parent_x, parent_y = self.find(x), self.find(y)\n",
    "        if parent_x != parent_y:\n",
    "            self.union(parent_x, parent_y)\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        # m, n = len(grid), len(grid[0])\n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         ch, target_pos = grid[i][j], (i, j)\n",
    "        #         q = deque([(i, j, 0, {(i, j)})])\n",
    "        #         while q:\n",
    "        #             x, y, distance, visited = q.popleft()\n",
    "        #             for xx, yy in ((x-1, y), (x+1, y), (x, y-1), (x, y+1)):\n",
    "        #                 if 0 <= xx < m and 0 <= yy < n and grid[xx][yy] == ch:\n",
    "        #                     if (xx, yy) == target_pos and distance >= 3:\n",
    "        #                         return True\n",
    "        #                     if (xx, yy) not in visited:\n",
    "        #                         q.append((xx, yy, distance+1, visited | {(xx, yy)}))\n",
    "        # return False\n",
    "\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        uf = UnionFind(m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i > 0 and grid[i][j] == grid[i - 1][j]:\n",
    "                    if not uf.find_union(i * n + j, (i - 1) * n + j):\n",
    "                        return True\n",
    "                if j > 0 and grid[i][j] == grid[i][j - 1]:\n",
    "                    if not uf.find_union(i * n + j, i * n + j - 1):\n",
    "                        return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, num):\n",
    "        self.num = num\n",
    "        self.size = [1] * num\n",
    "        self.parent = list(range(num))\n",
    "        self.count = num\n",
    "\n",
    "    def find_set(self, value):\n",
    "        if self.parent[value] == value:\n",
    "            return value\n",
    "        self.parent[value] = self.find_set(self.parent[value])\n",
    "        return self.parent[value]\n",
    "\n",
    "    def unite(self, x, y):\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.count -= 1\n",
    "\n",
    "    def find_unite(self, x, y):\n",
    "        x_parent, y_parent = self.find_set(x), self.find_set(y)\n",
    "\n",
    "        if x_parent != y_parent:\n",
    "            self.unite(x_parent, y_parent)\n",
    "            return True\n",
    "        print('x', x_parent)\n",
    "        print('y', y_parent)\n",
    "        print(self.size)\n",
    "        print(self.parent)\n",
    "        return False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        uf = UnionFind(m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j > 0 and grid[i][j] == grid[i][j - 1] and not uf.find_unite(i * n + j, i * n + j - 1):\n",
    "                    return True\n",
    "                if i > 0 and grid[i][j] == grid[i - 1][j] and not uf.find_unite(i * n + j, n * (i - 1) + j):\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    matrix = [[\"a\", \"a\", \"a\", \"a\"], [\"a\", \"b\", \"b\", \"a\"], [\"a\", \"b\", \"b\", \"a\"], [\"a\", \"a\", \"a\", \"a\"]]\n",
    "    solution = Solution()\n",
    "    result = solution.containsCycle(matrix)\n",
    "    print(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.parent = {}\n",
    "\n",
    "    def find(self, x):\n",
    "        self.parent.setdefault(x, x)\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "        \n",
    "    def union(self, x: int, y: int):\n",
    "        root_x, root_y = self.find(x), self.find(y)\n",
    "        if root_x != root_y:\n",
    "            self.parent[root_x] = root_y\n",
    "\n",
    "    def connected(self, x: int, y: int):\n",
    "        return self.find(x) == self.find(y)\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        uf = UnionFind()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                k = i * n + j\n",
    "                if i < m - 1 and grid[i+1][j] == grid[i][j]:\n",
    "                    if uf.connected(k, k+n):\n",
    "                        return True\n",
    "                    uf.union(k, k+n)\n",
    "                if j < n - 1 and grid[i][j+1] == grid[i][j]:\n",
    "                    if uf.connected(k, k+1):\n",
    "                        return True\n",
    "                    uf.union(k, k+1)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        # 移动的前提是值相同\n",
    "        dirc = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "        # 遍历一遍的复杂度在10^5次方级别\n",
    "        # 我想用BFS算\n",
    "        visited = [set() for _ in range(26)] \n",
    "\n",
    "        def bfs(i,j):\n",
    "            c = grid[i][j]\n",
    "            index = ord(c) - ord('a')\n",
    "            if (i,j) in visited[index]:\n",
    "                return False \n",
    "            visited[index].add((i,j))\n",
    "            q = deque()\n",
    "            q.append((i,j,i,j))\n",
    "\n",
    "            while q:\n",
    "                i,j,prei,prej = q.popleft()\n",
    "                for m,n in dirc:\n",
    "                    x = i+m\n",
    "                    y = j+n \n",
    "                    if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and (x,y) != (prei,prej) and grid[x][y] == c:\n",
    "                        if (x,y) in visited[index]:\n",
    "                            return True \n",
    "                        visited[index].add((x,y))\n",
    "                        q.append((x,y,i,j))\n",
    "            return False\n",
    "        \n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if bfs(i,j):\n",
    "                    return True \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "\n",
    "        # 寻找所有需要检查的字符\n",
    "        visited = collections.defaultdict(set)  # 需要检查的字符\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                value = grid[i][j]\n",
    "\n",
    "                # 判断当前位置是否已被查询过，如果已被查询过则跳过\n",
    "                if (i, j) in visited[value]:\n",
    "                    continue\n",
    "\n",
    "                # 如果没被查询过则检查是否存在环\n",
    "                new_visited = set()\n",
    "                positions = collections.deque([(None, (i, j))])\n",
    "\n",
    "                while positions:\n",
    "                    from_position, now_position = positions.popleft()\n",
    "\n",
    "                    if now_position not in new_visited:\n",
    "                        new_visited.add(now_position)\n",
    "                    else:\n",
    "                        # 如果检查出环则直接返回结果\n",
    "                        return True\n",
    "\n",
    "                    i, j = now_position\n",
    "                    if i > 0 and grid[i - 1][j] == value and from_position != (i - 1, j):\n",
    "                        positions.append(((i, j), (i - 1, j)))\n",
    "                    if i < n - 1 and grid[i + 1][j] == value and from_position != (i + 1, j):\n",
    "                        positions.append(((i, j), (i + 1, j)))\n",
    "                    if j > 0 and grid[i][j - 1] == value and from_position != (i, j - 1):\n",
    "                        positions.append(((i, j), (i, j - 1)))\n",
    "                    if j < m - 1 and grid[i][j + 1] == value and from_position != (i, j + 1):\n",
    "                        positions.append(((i, j), (i, j + 1)))\n",
    "\n",
    "                # 如果没有检查出环在，则记录检查过的点\n",
    "                visited[value] |= new_visited\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        ch=set()\n",
    "        vis=set()\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if (i,j) not in vis:\n",
    "                    t=grid[i][j]\n",
    "                    ch.add(grid[i][j])\n",
    "                    stack=collections.deque()\n",
    "                    stack.append([i,j,-1,-1])\n",
    "              \n",
    "                  \n",
    "                    while stack:\n",
    "                        x,y,fx,fy=stack.popleft()\n",
    "                        if (x,y) in vis:\n",
    "                            return True\n",
    "                        vis.add((x,y))\n",
    "                        for x1,y1 in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:\n",
    "                            if 0<=x1<m and 0<=y1<n and grid[x1][y1]==t:\n",
    "                                if x1==fx and y1==fy:\n",
    "                                    continue\n",
    "                                if (x1,y1) in vis:\n",
    "                                    return True\n",
    "                                else:\n",
    "                                    stack.append([x1,y1,x,y])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        vst=[[False for _ in range(n)] for _ in range(m)]\n",
    "        fa=[i for i in range(m*n)]\n",
    "        def find(x):\n",
    "            if x==fa[x]: return x\n",
    "            fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(x,y):\n",
    "            fa[find(y)]=find(x)\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                vst[x][y]=True\n",
    "                for d in [[0,1],[0,-1],[1,0],[-1,0]]:\n",
    "                    nx,ny=x+d[0],y+d[1]\n",
    "                    if nx<0 or ny<0 or nx>=m or ny>=n or grid[nx][ny]!=grid[x][y] or vst[nx][ny]: continue\n",
    "                    if find(nx*n+ny)==find(x*n+y): return True\n",
    "                    union(x*n+y,nx*n+ny)\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        '''并查集判断'''\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        vst=[[False for _ in range(n)] for _ in range(m)]\n",
    "        fa=[i for i in range(m*n)]\n",
    "        def getid(i,j):\n",
    "            return i*n+j\n",
    "        def find(x):\n",
    "            if fa[x]==x:\n",
    "                return x\n",
    "            fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(x,y):\n",
    "            fa[find(x)]=find(y)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not vst[i][j]:\n",
    "                    vst[i][j]=True\n",
    "                    for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:\n",
    "                        if x>=0 and x<m and y>=0 and y<n and grid[x][y]==grid[i][j] and not vst[x][y]:\n",
    "                            id1=getid(x,y)\n",
    "                            id2=getid(i,j)\n",
    "                            if find(id1)==find(id2):\n",
    "                                return True\n",
    "                            else:\n",
    "                                union(id1,id2)\n",
    "        return False\n",
    "\n",
    "                             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        '''并查集判断'''\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        vst=[[False for _ in range(n)] for _ in range(m)]\n",
    "        fa=[i for i in range(m*n)]\n",
    "        def getid(i,j):\n",
    "            return i*n+j\n",
    "        def find(x):\n",
    "            if fa[x]==x:\n",
    "                return x\n",
    "            fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(x,y):\n",
    "            fa[find(x)]=find(y)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not vst[i][j]:\n",
    "                    vst[i][j]=True\n",
    "                    for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:\n",
    "                        if x>=0 and x<m and y>=0 and y<n and grid[x][y]==grid[i][j] and not vst[x][y]:\n",
    "                            id1=getid(x,y)\n",
    "                            id2=getid(i,j)\n",
    "                            if find(id1)==find(id2):#已经连通，在连通成环\n",
    "                                return True\n",
    "                            else:\n",
    "                                union(id1,id2)\n",
    "        return False\n",
    "\n",
    "                             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "    \n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        fa = [i for i in range(m*n)]\n",
    "        directions = [[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        visited = [[False for _ in range(n)] for _ in range(m)]\n",
    "        def find(x):\n",
    "            if x==fa[x]: return x\n",
    "            fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        \n",
    "        def union(x,y):\n",
    "            fa[find(x)] = find(y)\n",
    "        \n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                visited[i][j] = True\n",
    "                for d in directions:\n",
    "                    nx = i + d[0]\n",
    "                    ny = j + d[1]\n",
    "                    index1 = i*n + j\n",
    "                    index2 = nx*n +ny\n",
    "                    \n",
    "\n",
    "                    if nx<0 or ny<0 or nx>=m or ny>=n or grid[i][j]!=grid[nx][ny] or visited[nx][ny]:\n",
    "                        continue\n",
    "                    \n",
    "                    if find(index1)==find(index2): return True\n",
    "\n",
    "                    union(index1,index2)\n",
    "        \n",
    "        return False\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        n , m = len(grid) , len(grid[0])\n",
    "        c = 0\n",
    "        count = [[0] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                count[i][j] = c\n",
    "                c += 1\n",
    "        djs = list(range(c))\n",
    "        def find(x:int)->int:\n",
    "            if djs[x] != x:\n",
    "                djs[x] = find(djs[x])\n",
    "            return djs[x]\n",
    "        def union(x:int,y:int)->None:\n",
    "            djs[find(x)] = find(y)\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if j+1 < m and grid[i][j] == grid[i][j+1]:\n",
    "                    if find(count[i][j]) == find(count[i][j+1]):\n",
    "                        return True\n",
    "                    else:\n",
    "                        union(count[i][j],count[i][j+1])\n",
    "                if i+1 < n and grid[i][j] == grid[i+1][j]:\n",
    "                    if find(count[i][j]) == find(count[i+1][j]):\n",
    "                        return True\n",
    "                    else:\n",
    "                        union(count[i][j],count[i+1][j])\n",
    "\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#为什么可以用并查集判断环：两个相连的点还没union就已经同属一个parent-存在环\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        parents = [i for i in range(m*n)]\n",
    "        def find(x):\n",
    "            parent = parents[x]\n",
    "            while parent != x:\n",
    "                return find(parent)\n",
    "            return parent\n",
    "        def union(x,y):\n",
    "            parent_x, parent_y = find(x),find(y)\n",
    "            if parent_x == parent_y:\n",
    "                return False\n",
    "            parents[parent_x] = parent_y\n",
    "            return True\n",
    "        def position(i,j):\n",
    "            return i*n+j\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j<n-1 and grid[i][j] == grid[i][j+1]:\n",
    "                    if not union(position(i,j),position(i,j+1)):\n",
    "                        return True\n",
    "                if i<m-1 and grid[i][j] == grid[i+1][j]:\n",
    "                    if not union(position(i,j),position(i+1,j)):\n",
    "                        return True\n",
    "        return False\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        # 循环寻找根植\n",
    "        def getroot(x):\n",
    "            while father[x] != x:\n",
    "                x = getroot(father[x])\n",
    "            return x\n",
    "\n",
    "        # 比较新的路径起点和终点，如果根植相同，证明有环，否则更新终点的根植\n",
    "        def union(s, t):\n",
    "            rs, rt = getroot(s), getroot(t)\n",
    "            if rs == rt:\n",
    "                return True\n",
    "            father[rt] = rs\n",
    "            return False\n",
    "\n",
    "        # 由上而下，由左往右更新根植，如果发现环即返回，否则表示无环\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        father = [i for i in range(m*n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i > 0 and grid[i][j] == grid[i-1][j]:\n",
    "                    if union(i*n+j, (i-1)*n+j):\n",
    "                        return True\n",
    "                if j > 0 and grid[i][j] == grid[i][j-1]:\n",
    "                    if union(i*n+j, i*n+(j-1)):\n",
    "                        return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        # 循环寻找根植\n",
    "        def getroot(x):\n",
    "            while father[x] != x:\n",
    "                x = getroot(father[x])\n",
    "            return x\n",
    "\n",
    "        # 比较新的路径起点和终点，如果根植相同，证明有环，否则更新终点的根植\n",
    "        def union(s, t):\n",
    "            rs, rt = getroot(s), getroot(t)\n",
    "            if rs == rt:\n",
    "                return True\n",
    "            father[rt] = rs\n",
    "            return False\n",
    "\n",
    "        # 由上而下，由左往右更新根植，如果发现环即返回，否则表示无环\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        father = [i for i in range(m*n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i > 0 and grid[i][j] == grid[i-1][j]:\n",
    "                    if union(i*n+j, (i-1)*n+j):\n",
    "                        return True\n",
    "                if j > 0 and grid[i][j] == grid[i][j-1]:\n",
    "                    if union(i*n+j, i*n+(j-1)):\n",
    "                        return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        # 循环寻找根植\n",
    "        def getroot(x):\n",
    "            while father[x] != x:\n",
    "                x = getroot(father[x])\n",
    "            return x\n",
    "\n",
    "        # 比较新的路径起点和终点，如果根植相同，证明有环，否则更新终点的根植\n",
    "        def union(s, t):\n",
    "            rs, rt = getroot(s), getroot(t)\n",
    "            if rs == rt:\n",
    "                return True\n",
    "            father[rt] = rs\n",
    "            return False\n",
    "\n",
    "        # 由上而下，由左往右更新根植，如果发现环即返回，否则表示无环\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        father = [i for i in range(m*n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i > 0 and grid[i][j] == grid[i-1][j]:\n",
    "                    if union(i*n+j, (i-1)*n+j):\n",
    "                        return True\n",
    "                if j > 0 and grid[i][j] == grid[i][j-1]:\n",
    "                    if union(i*n+j, i*n+(j-1)):\n",
    "                        return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        def find(x):\n",
    "            if p[x]!=x:\n",
    "                p[x]=find(p[x])\n",
    "            return p[x]\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        p=list(range(m*n))\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for a,b in [[0,1],[1,0]]:\n",
    "                    x,y=i+a,j+b\n",
    "                    if x < m and y < n and grid[x][y] == grid[i][j]:\n",
    "                        if find(x * n + y) == find(i * n + j):\n",
    "                            return True\n",
    "                        p[find(x * n + y)] = find(i * n + j)\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0]) \n",
    "        g = [[] for _ in range(m * n)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                curr = grid[i][j]\n",
    "                for x, y in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y] == curr:\n",
    "                        g[i * n + j].append(x * n + y)\n",
    "        \n",
    "        vis = set()\n",
    "        for i in range(m * n):\n",
    "            if i not in vis:\n",
    "                queue = deque([i])\n",
    "                last = set()\n",
    "                while queue:\n",
    "                    now = set()\n",
    "                    for z in range(len(queue)):\n",
    "                        node = queue.popleft()\n",
    "                        now.add(node)\n",
    "                        for j in g[node]:\n",
    "                            if j not in last:\n",
    "                                if j in vis:\n",
    "                                    return True\n",
    "                                vis.add(j)\n",
    "                                queue.append(j)\n",
    "                    last = now\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "        self.part = n\n",
    "        return\n",
    "\n",
    "    def find(self, x):\n",
    "        lst = []\n",
    "        while x != self.root[x]:\n",
    "            lst.append(x)\n",
    "            # 在查询的时候合并到顺带直接根节点\n",
    "            x = self.root[x]\n",
    "        for w in lst:\n",
    "            self.root[w] = x\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] >= self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        # 将非根节点的秩赋0\n",
    "        self.size[root_x] = 0\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_root_part(self):\n",
    "        # 获取每个根节点对应的组\n",
    "        part = defaultdict(list)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "\n",
    "    def get_root_size(self):\n",
    "        # 获取每个根节点对应的组大小\n",
    "        size = defaultdict(int)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            size[self.find(i)] = self.size[self.find(i)]\n",
    "        return size\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        edges = []\n",
    "        uf = UnionFind(m*n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                w = grid[i][j]\n",
    "                for x, y in [[i+1, j], [i, j+1]]:\n",
    "                    if 0<=x<m and 0<=y<n and grid[x][y] == w:\n",
    "                        uf.union(i*n+j, x*n+y)\n",
    "                        edges.append([i*n+j, x*n+y])\n",
    "        dct = defaultdict(int)\n",
    "        for i, j in edges:\n",
    "            dct[uf.find(i)] += 1\n",
    "        group = uf.get_root_part()\n",
    "        for r in group:\n",
    "            if  dct[uf.find(r)] >= len(group[r]) >= 4:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dx = [-1, 0, 1, 0]\n",
    "dy = [0, 1, 0, -1]\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visit = [[False for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        def dfs(x, y, pos):\n",
    "            visit[x][y] = True\n",
    "            for i in range(4):\n",
    "                nx = x + dx[i]\n",
    "                ny = y + dy[i]\n",
    "                if nx * m + ny == pos:\n",
    "                    continue\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == grid[x][y]:\n",
    "                    if visit[nx][ny]:\n",
    "                        return True\n",
    "                    if dfs(nx, ny, x * m + y):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not visit[i][j]:\n",
    "                    if dfs(i, j, -1):\n",
    "                        return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dx = [-1, 0, 1, 0]\n",
    "dy = [0, 1, 0, -1]\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visit = [[False for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        def dfs(x, y, pos):\n",
    "            visit[x][y] = True\n",
    "            for i in range(4):\n",
    "                nx = x + dx[i]\n",
    "                ny = y + dy[i]\n",
    "                if nx * n + ny == pos:\n",
    "                    continue\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == grid[x][y]:\n",
    "                    if visit[nx][ny]:\n",
    "                        return True\n",
    "                    if dfs(nx, ny, x * n + y):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not visit[i][j]:\n",
    "                    if dfs(i, j, -1):\n",
    "                        return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dirs = [[1,0],[-1,0],[0,1],[0,-1]]\n",
    "        visit = [[False for i in range(n)] for j in range(m)] \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if visit[i][j] != True and self.dfs(i, j, -1, -1, visit, dirs,grid, grid[i][j]):\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "    def dfs(self,x,y, px,py, vst ,dirs,grid,char):\n",
    "        if vst[x][y] == True:\n",
    "            return True\n",
    "        vst[x][y] = True\n",
    "        for dirr in dirs:\n",
    "            nx = x + dirr[0]\n",
    "            ny = y+dirr[1]\n",
    "            if (nx <0 or ny < 0 or nx >= len(vst) or ny >= len(vst[0]) or (px==nx and py ==ny) or grid[nx][ny] != char ):\n",
    "                continue\n",
    "            else:\n",
    "                if self.dfs(nx, ny, x, y, vst, dirs ,grid, char):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        visited = [[0]*m for _ in range(n)]\n",
    "        move = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n",
    "        def dfs(start, node, pre):\n",
    "            if visited[node[0]][node[1]] == 1:\n",
    "                return True\n",
    "            # if visited[node[0]][node[1]] == 1:\n",
    "            #     return False\n",
    "            visited[node[0]][node[1]] = 1\n",
    "            for i in move:\n",
    "                x = node[0]+i[0]\n",
    "                y = node[1]+i[1]\n",
    "                if 0<=x<n and 0<=y<m:\n",
    "                    if x==pre[0] and y==pre[1]:\n",
    "                        continue\n",
    "                    if grid[x][y] == grid[start[0]][start[1]]:\n",
    "                        if dfs(start, [x, y], node):\n",
    "                            return True\n",
    "            return False\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if visited[i][j] == 0:\n",
    "                    ans = dfs([i, j], [i, j], [-1, -1])   \n",
    "                    if ans == True:\n",
    "                        return True\n",
    "        return False\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        visited = [[0]*m for _ in range(n)]\n",
    "        move = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n",
    "        def dfs(node, pre):\n",
    "            if visited[node[0]][node[1]] == 1:\n",
    "                return True\n",
    "            # if visited[node[0]][node[1]] == 1:\n",
    "            #     return False\n",
    "            visited[node[0]][node[1]] = 1\n",
    "            for i in move:\n",
    "                x = node[0]+i[0]\n",
    "                y = node[1]+i[1]\n",
    "                if 0<=x<n and 0<=y<m:\n",
    "                    if x==pre[0] and y==pre[1]:\n",
    "                        continue\n",
    "                    if grid[x][y] == grid[node[0]][node[1]]:\n",
    "                        if dfs([x, y], node):\n",
    "                            return True\n",
    "            return False\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if visited[i][j] == 0:\n",
    "                    ans = dfs([i, j], [-1, -1])   \n",
    "                    if ans == True:\n",
    "                        return True\n",
    "        return False\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        flag = [[0] * n for _ in range(m)]\n",
    "\n",
    "        def dfs(r, c, pre_r, pre_c):\n",
    "            result = False\n",
    "            for i, j in ((-1, 0), (1, 0), (0, -1), (0, 1)):\n",
    "                next_r, next_c = r + i, c + j\n",
    "                if 0 <= next_r < m and 0 <= next_c < n and grid[next_r][next_c] == grid[r][c]:\n",
    "                    if flag[next_r][next_c] == 0:\n",
    "                        flag[next_r][next_c] = 1\n",
    "                        result = result or dfs(next_r, next_c, r, c)\n",
    "                    elif next_r != pre_r and next_c != pre_c:\n",
    "                        result = True\n",
    "            return result\n",
    "\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if flag[r][c] == 0:\n",
    "                    flag[r][c] = 1\n",
    "                    if dfs(r, c, -1, -1):\n",
    "                        return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "        vis = [[False] * n for _ in range(m)]\n",
    "        \n",
    "        def dfs(x, y, px, py):\n",
    "            vis[x][y] = True\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx <= m-1 and 0 <= ny <= n-1 and (nx != px or ny != py ) and grid[nx][ny] == grid[x][y]:\n",
    "                    if vis[nx][ny]:\n",
    "                        return True\n",
    "                    else:\n",
    "                        if dfs(nx, ny, x, y):\n",
    "                            return True\n",
    "            return False\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if vis[i][j] == False:\n",
    "                    if dfs(i, j, -1, -1):\n",
    "                        return True\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        \n",
    "        # Depth First Search function\n",
    "        def dfs(i, j, prev_i, prev_j):\n",
    "            # If this cell has been visited before\n",
    "            if visited[i][j]:\n",
    "                return True\n",
    "            \n",
    "            visited[i][j] = True\n",
    "            \n",
    "            for x, y in directions:\n",
    "                ni, nj = i + x, j + y\n",
    "                \n",
    "                # Check for valid cell\n",
    "                if 0 <= ni < m and 0 <= nj < n and (ni, nj) != (prev_i, prev_j) and grid[ni][nj] == grid[i][j]:\n",
    "                    if dfs(ni, nj, i, j):\n",
    "                        return True\n",
    "            \n",
    "            return False\n",
    "        \n",
    "        # Traverse each cell in the grid\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not visited[i][j] and dfs(i, j, -1, -1):\n",
    "                    return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        i_len=len(grid)\n",
    "        j_len=len(grid[0])\n",
    "        visited=[[False]*len(grid[0]) for i in range(len(grid))]\n",
    "        tables=[[1,0],[0,1],[-1,0],[0,-1]]\n",
    "        def visit(begin,before):\n",
    "            i=begin[0]\n",
    "            j=begin[1]\n",
    "            char=grid[i][j]\n",
    "            if(visited[i][j]==True):return False\n",
    "            visited[i][j]=True\n",
    "            for table in tables:\n",
    "                tmp_i=i+table[0]\n",
    "                tmp_j=j+table[1]\n",
    "                if(tmp_i<0 or tmp_j<0 or tmp_i>=i_len or tmp_j>=j_len):\n",
    "                    continue\n",
    "                if(tmp_i==before[0] and tmp_j==before[1]):continue\n",
    "                if(grid[tmp_i][tmp_j]==grid[i][j]):\n",
    "                    if(visited[tmp_i][tmp_j]):\n",
    "                        # print(visited,i,j,tmp_i,tmp_j)\n",
    "                        return True\n",
    "                    tmp_ans=visit([tmp_i,tmp_j],[i,j])\n",
    "                    if(tmp_ans):return True\n",
    "        for i in range(i_len):\n",
    "            for j in range(j_len):\n",
    "                if(visit([i,j],[-1,-1])):return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        flag = [[0] * n for _ in range(m)]\n",
    "\n",
    "        def dfs(r, c, pre_r, pre_c):\n",
    "            result = False\n",
    "            for i, j in ((-1, 0), (1, 0), (0, -1), (0, 1)):\n",
    "                next_r, next_c = r + i, c + j\n",
    "                if 0 <= next_r < m and 0 <= next_c < n and grid[next_r][next_c] == grid[r][c]:\n",
    "                    if flag[next_r][next_c] == 0:\n",
    "                        flag[next_r][next_c] = 1\n",
    "                        result = result or dfs(next_r, next_c, r, c)\n",
    "                    elif next_r != pre_r and next_c != pre_c:\n",
    "                        result = True\n",
    "            return result\n",
    "\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if flag[r][c] == 0:\n",
    "                    flag[r][c] = 1\n",
    "                    if dfs(r, c, -1, -1):\n",
    "                        return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        # Do not need to backtrack!\n",
    "        def dfs(lasti, lastj, i, j):\n",
    "            nonlocal ok\n",
    "            if ok:\n",
    "                return\n",
    "            if visited[i][j]:\n",
    "                ok = True\n",
    "                return\n",
    "            visited[i][j] = 1\n",
    "            for dx, dy in [(1,0),(-1,0),(0,1),(0,-1)]:\n",
    "                if (i + dx, j + dy) != (lasti, lastj):\n",
    "                    newi = i+dx\n",
    "                    newj = j+dy\n",
    "                    if 0 <= newi < m and 0 <= newj < n and grid[newi][newj] == grid[i][j]:\n",
    "                        dfs(i, j, newi, newj)\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ok = False\n",
    "                if not visited[i][j]:\n",
    "                    dfs(-1, -1, i, j)\n",
    "                if ok: return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        ans=False\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        ll=[[-1,0],[1,0],[0,-1],[0,1]]\n",
    "\n",
    "        def dfs(i,j,fa):\n",
    "            nonlocal ans\n",
    "            visited[i][j]=1\n",
    "\n",
    "            for ii,jj in ll:\n",
    "                newi,newj=i+ii,j+jj\n",
    "                if 0<=newi<m and 0<=newj<n:\n",
    "                    if (newi,newj)==fa:continue\n",
    "                    if grid[newi][newj]!=grid[i][j]:continue\n",
    "                    if visited[newi][newj]:\n",
    "                        ans=True\n",
    "                        return\n",
    "                    dfs(newi,newj,(i,j))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        visited=[[0]*n for i in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if visited[i][j]:continue\n",
    "                dfs(i,j,(-1,-1))\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        dirc = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "\n",
    "        def dfs(i, j, previ, prevj):\n",
    "            visited[i][j] = True\n",
    "            for di, dj in dirc:\n",
    "                ni, nj = di + i, dj + j\n",
    "                if 0 <= ni < m and 0 <= nj < n and [ni, nj] != [previ, prevj] and grid[ni][nj] == grid[i][j]:\n",
    "                    # print(ni, nj)\n",
    "                    if visited[ni][nj]:\n",
    "                        return True\n",
    "                    elif dfs(ni, nj, i, j):\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not visited[i][j]:\n",
    "                    if dfs(i, j, -1, -1):\n",
    "                        # print(i, j, grid[i][j])\n",
    "                        return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        ans=False\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        ll=[[-1,0],[1,0],[0,-1],[0,1]]\n",
    "\n",
    "        def dfs(i,j,fa):\n",
    "            nonlocal ans\n",
    "            visited[i][j]=1\n",
    "\n",
    "            for ii,jj in ll:\n",
    "                newi,newj=i+ii,j+jj\n",
    "                if 0<=newi<m and 0<=newj<n:\n",
    "                    if (newi,newj)==fa:continue\n",
    "                    if grid[newi][newj]!=grid[i][j]:continue\n",
    "                    if visited[newi][newj]:\n",
    "                        ans=True\n",
    "                        return\n",
    "                    dfs(newi,newj,(i,j))\n",
    "            # visited[i][j]=0\n",
    "\n",
    "\n",
    "\n",
    "        visited=[[0]*n for i in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if ans:return ans\n",
    "                if visited[i][j]:continue\n",
    "                dfs(i,j,(-1,-1))\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        i_len=len(grid)\n",
    "        j_len=len(grid[0])\n",
    "        visited=[[False]*len(grid[0]) for i in range(len(grid))]\n",
    "        tables=[[1,0],[0,1],[-1,0],[0,-1]]\n",
    "        def visit(begin,before):\n",
    "            i=begin[0]\n",
    "            j=begin[1]\n",
    "            char=grid[i][j]\n",
    "            if(visited[i][j]==True):return False\n",
    "            visited[i][j]=True\n",
    "            for table in tables:\n",
    "                tmp_i=i+table[0]\n",
    "                tmp_j=j+table[1]\n",
    "                if(tmp_i<0 or tmp_j<0 or tmp_i>=i_len or tmp_j>=j_len):\n",
    "                    continue\n",
    "                if(tmp_i==before[0] and tmp_j==before[1]):continue\n",
    "                if(grid[tmp_i][tmp_j]==grid[i][j]):\n",
    "                    if(visited[tmp_i][tmp_j]):\n",
    "                        print(visited,i,j,tmp_i,tmp_j)\n",
    "                        return True\n",
    "                    tmp_ans=visit([tmp_i,tmp_j],[i,j])\n",
    "                    if(tmp_ans):return True\n",
    "        for i in range(i_len):\n",
    "            for j in range(j_len):\n",
    "                if(visit([i,j],[-1,-1])):return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "    \n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        directions = [[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        visited = [[False for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "\n",
    "        # prev is to ensure that you are not going back\n",
    "        def dfs(x,y,px,py,c):\n",
    "            if visited[x][y]: return True\n",
    "\n",
    "            visited[x][y] = True\n",
    "\n",
    "            for d in directions:\n",
    "                nx = x + d[0]\n",
    "                ny = y + d[1]\n",
    "                if nx<0 or ny<0 or nx>=m or ny>=n or (px==nx and py==ny) or grid[nx][ny]!=c:\n",
    "                    continue\n",
    "                if(dfs(nx,ny,x,y,c)):\n",
    "                    return True\n",
    "            \n",
    "            return False\n",
    "        \n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if(not visited[i][j]):\n",
    "                    if dfs(i,j,-1,-1,grid[i][j]):\n",
    "                        return True\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        visted = [[0]*n for _ in range(m)]\n",
    "        def dfs(x,y,cnt):\n",
    "            if visted[x][y] != 0:\n",
    "                return cnt-visted[x][y] >= 4\n",
    "            visted[x][y] = cnt\n",
    "            direct = ((0,1),(0,-1),(1,0),(-1,0))\n",
    "            for dx,dy in direct:\n",
    "                nx,ny = x+dx,y+dy\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[x][y] == grid[nx][ny]:\n",
    "                    if dfs(nx,ny,cnt+1):\n",
    "                        return True\n",
    "            return False\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if visted[x][y] == 0 and dfs(x,y,1):\n",
    "                    return True\n",
    "        return False\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        vst=[[False for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        def dfs(i,j,pi,pj):\n",
    "            if vst[i][j]:#遇到环路了\n",
    "                return True\n",
    "            vst[i][j]=True\n",
    "            for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:\n",
    "                if x>=0 and x<m and y>=0 and y<n and (x!=pi or y!=pj) and grid[x][y]==grid[i][j]:\n",
    "                    if dfs(x,y,i,j):\n",
    "                        return True\n",
    "            return False\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not vst[i][j]:\n",
    "                    if dfs(i,j,-1,-1):\n",
    "                        return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        vst = [[0] * n for _ in range(m)]\n",
    "\n",
    "        def dfs(x, y, prex, prey, c):\n",
    "            if vst[x][y]:\n",
    "                return True\n",
    "            vst[x][y] = 1\n",
    "            for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "                if 0 <= nx < m and 0 <= ny < n and (nx != prex or ny != prey) and grid[nx][ny] == c:\n",
    "                    if dfs(nx, ny, x, y, c):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if vst[i][j] == 0 and dfs(i, j, -1, -1, grid[i][j]):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        if not grid:\n",
    "            return False\n",
    "\n",
    "        rows = len(grid)\n",
    "        cols = len(grid[0])\n",
    "        visited = set()\n",
    "\n",
    "        def dfs(x, y, parent):\n",
    "            if (x, y) in visited:\n",
    "                return True\n",
    "\n",
    "            visited.add((x, y))\n",
    "            for direct in [(-1, 0), (0, -1), (1, 0), (0, 1)]:\n",
    "                new_x = x + direct[0]\n",
    "                new_y = y + direct[1]\n",
    "                if new_x < 0 or new_x >= rows or new_y < 0 or new_y >= cols:\n",
    "                    continue\n",
    "\n",
    "                if (new_x, new_y) != parent and grid[new_x][new_y] == grid[x][y]:\n",
    "                    if dfs(new_x, new_y, (x, y)):\n",
    "                        return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        for row in range(rows):\n",
    "            for col in range(cols):\n",
    "                if (row, col) not in visited and dfs(row, col, None):\n",
    "                    return True\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        def dfs(x,y,grid,px,py,vis):\n",
    "            if vis[x][y] == 1:\n",
    "                return True\n",
    "            vis[x][y] = 1\n",
    "            for dx,dy in [[0,1],[0,-1],[1,0],[-1,0]]:\n",
    "                nx,ny = dx+x, dy+y\n",
    "                if nx>=0 and nx<len(grid) and ny>=0 and ny<len(grid[0]) and grid[nx][ny]==grid[x][y] and [nx,ny] != [px,py]:\n",
    "                    if dfs(nx,ny,grid,x,y,vis):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        vis = [[0]*len(grid[0]) for _ in range(len(grid))]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if vis[i][j]==0 and dfs(i,j,grid,-1,-1,vis):\n",
    "                    return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        vst=[[False for _ in range(n)] for _ in range(m)]\n",
    "        res=[]\n",
    "        def dfs(x,y,exc):\n",
    "            if vst[x][y]:\n",
    "                res.append(1)\n",
    "                return\n",
    "            vst[x][y]=True\n",
    "            dircs=[[1,0],[-1,0],[0,1],[0,-1]]\n",
    "            if exc: dircs.remove(exc)\n",
    "            for dirc in dircs:\n",
    "                nx,ny=x+dirc[0],y+dirc[1]\n",
    "                if nx<0 or ny<0 or nx>=m or ny>=n or grid[nx][ny]!=grid[x][y]: continue\n",
    "                dfs(nx,ny,[-dirc[0],-dirc[1]])\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if vst[x][y]: continue\n",
    "                dfs(x,y,[])\n",
    "        if res: return True\n",
    "        else: return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        vis = [[0] * n for _ in range(m)]\n",
    "        def dfs(i, j, cnt):\n",
    "            if vis[i][j] != 0:\n",
    "                return cnt - vis[i][j] >= 4\n",
    "            vis[i][j] = cnt\n",
    "            for dx, dy in [[0, 1], [0, -1], [1, 0], [-1, 0]]:\n",
    "                x, y = i + dx, j + dy\n",
    "                if 0 <= x < m and 0 <= y < n and grid[x][y] == grid[i][j]:\n",
    "                    if dfs(x, y, cnt + 1):\n",
    "                        return True\n",
    "            return False\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if vis[x][y] == 0 and dfs(x, y, 0):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        \n",
    "        r, c = len(grid), len(grid[0])\n",
    "        seen = set()\n",
    "        \n",
    "        def dfs(ci,cj,pi,pj, mark):\n",
    "            seen.add((ci, cj))\n",
    "\n",
    "            for di, dj in [(1,0),(-1,0),(0,-1),(0,1)]:\n",
    "                newi, newj = ci + di, cj + dj\n",
    "                if (0<=newi<r and 0<=newj<c) and (newi != pi or newj != pj) and grid[newi][newj] == mark:\n",
    "                    if (newi, newj) in seen:\n",
    "                        return True\n",
    "                    else:\n",
    "                        if dfs(newi, newj, ci, cj, mark):\n",
    "                            return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if (i, j) not in seen:\n",
    "                    if dfs(i, j, -10, -10, grid[i][j]):\n",
    "                        return True\n",
    "\n",
    "\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "#         def check_ring(pos, last_pos, a) -> bool:\n",
    "#             nonlocal visited\n",
    "#             nonlocal temp\n",
    "#             if pos in temp:\n",
    "#                 return True\n",
    "#             i, j = pos\n",
    "#             visited.add(pos)\n",
    "#             temp.add(pos)\n",
    "#             for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "#                 if 0 <= x < m and 0 <= y < n and (x, y) != last_pos and grid[x][y] == a:\n",
    "#                     val = check_ring((x, y), (i, j), a)\n",
    "#                     if val == True:\n",
    "#                         return True\n",
    "#             return False\n",
    "        \n",
    "#         m, n = len(grid), len(grid[0])\n",
    "#         visited = set()\n",
    "#         for i in range(m):\n",
    "#             for j in range(n):\n",
    "#                 if (i, j) in visited:\n",
    "#                     continue\n",
    "#                 visited.add((i, j))\n",
    "#                 temp = set()\n",
    "#                 temp.add((i, j))\n",
    "#                 a = grid[i][j]\n",
    "\n",
    "#                 for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "#                     if 0 <= x < m and 0 <= y < n and (x, y) not in visited and grid[x][y] == a:\n",
    "#                         if check_ring((x, y), (i, j), a):\n",
    "#                             return True\n",
    "#         return False\n",
    "\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool: \n",
    "        sys.setrecursionlimit(150000)\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        seen = set()\n",
    "        def dfs(node, p):\n",
    "            if node in seen: return True\n",
    "            seen.add(node)\n",
    "            i, j = node\n",
    "            for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:\n",
    "                if 0 <= x < m and 0 <= y < n and (x, y) != p and grid[x][y] == grid[i][j]:\n",
    "                    if dfs((x, y), node): return True\n",
    "            return False\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if (i, j) not in seen and dfs((i, j), None):\n",
    "                    return True\n",
    "        \n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class UnionFind:\n",
    "#     def __init__(self, n):\n",
    "#         self.n = n\n",
    "#         self.parent = list(range(n))\n",
    "#         self.setsCount = n\n",
    "#         self.size = [1] * n\n",
    "#     def findset(self, x):\n",
    "#         if self.parent[x] == x:\n",
    "#             return x\n",
    "#         self.parent[x] = self.findset(self.parent[x])\n",
    "#         return self.parent[x]\n",
    "#     def unite(self, x, y):\n",
    "#         if self.size[x] < self.size[y]:\n",
    "#             x, y = y, x\n",
    "#         self.parent[y] = x\n",
    "#         self.size[x] += self.size[y]\n",
    "#         self.setCount -= 1\n",
    "class Solution:\n",
    "    def containsCycle(self, grid: List[List[str]]) -> bool:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        visited = set()\n",
    "        def dfs(node, p):\n",
    "            if node in visited:\n",
    "                return True\n",
    "            visited.add(node)\n",
    "            x, y = node\n",
    "            for dx, dy in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:\n",
    "                if 0 <= dx < m and 0 <= dy < n and (dx, dy) != p and grid[dx][dy] == grid[x][y]:\n",
    "                    if dfs((dx, dy), node):\n",
    "                        return True\n",
    "            return False\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if (i, j) not in visited and dfs((i, j), None):\n",
    "                    return True\n",
    "        return False   "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
